Product Code Database
Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of to fill connected, similarly colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. A variant called boundary fill uses the same algorithms but is defined as the area connected to a given node that does not have a particular attribute.
Note that flood filling is not suitable for drawing filled polygons, as it will miss some pixels in more acute corners. Instead, see Even-odd rule and Nonzero-rule.
In order to generalize the algorithm in the common way, the following descriptions will instead have two routines available. One called Inside which returns true for unfilled points that, by their color, would be inside the filled area, and one called Set which fills a pixel/node. Any node that has Set called on it must then no longer be Inside.
Depending on whether we consider nodes touching at the corners connected or not, we have two variations: eight-way and four-way respectively.
'''Flood-fill''' (node):
1. If ''node'' is not ''Inside'' return.
2. ''Set'' the ''node''
3. Perform '''Flood-fill''' one step to the south of ''node''.
4. Perform '''Flood-fill''' one step to the north of ''node''
5. Perform '''Flood-fill''' one step to the west of ''node''
6. Perform '''Flood-fill''' one step to the east of ''node''
7. Return.
Though easy to understand, the implementation of the algorithm used above is impractical in languages and environments where stack space is severely constrained (e.g. ).
'''Flood-fill''' (node):
1. Set ''Q'' to the empty queue or stack.
2. Add ''node'' to the end of ''Q''.
3. While ''Q'' is not empty:
4. Set ''n'' equal to the first element of ''Q''.
5. Remove first element from ''Q''.
6. If ''n'' is ''Inside'':
''Set'' the ''n''
Add the node to the west of ''n'' to the end of ''Q''.
Add the node to the east of ''n'' to the end of ''Q''.
Add the node to the north of ''n'' to the end of ''Q''.
Add the node to the south of ''n'' to the end of ''Q''.
7. Continue looping until ''Q'' is exhausted.
8. Return.
As an optimisation, the scan algorithm does not need restart from every seed point, but only those at the start of the next span. Using a stack explores spans depth first, whilst a queue explores spans breadth first.
fn '''fill'''(''x'', ''y''):
if not '''Inside'''(''x'', ''y'') then return
let ''s'' = new empty stack or queue
Add (''x'', ''y'') to ''s''
while ''s'' is not empty:
Remove an (''x'', ''y'') from ''s''
let ''lx'' = ''x''
while '''Inside'''(''lx'' - 1, ''y''):
'''Set'''(''lx'' - 1, ''y'')
''lx'' = ''lx'' - 1
while '''Inside'''(''x'', ''y''):
'''Set'''(''x'', ''y'')
''x'' = ''x'' + 1
'''scan'''(''lx'', ''x'' - 1, ''y'' + 1, ''s'')
'''scan'''(''lx'', ''x'' - 1, ''y'' - 1, ''s'')
fn '''scan'''(''lx'', ''rx'', ''y'', ''s''):
let ''span_added'' = ''false''
for ''x'' in ''lx'' .. ''rx'':
if not '''Inside'''(''x'', ''y''):
''span_added'' = ''false''
else if not ''span_added'':
Add (''x'', ''y'') to ''s''
''span_added'' = ''true''
Over time, the following optimizations were realized:
The final, combined-scan-and-fill span filler was then published in 1990. In pseudo-code form:
fn '''fill'''(''x'', ''y''):
if not '''Inside'''(''x'', ''y'') then return
let ''s'' = new empty queue or stack
Add (''x'', ''x'', ''y'', 1) to ''s''
Add (''x'', ''x'', ''y'' - 1, -1) to ''s''
while ''s'' is not empty:
Remove an (''x1'', ''x2'', ''y'', ''dy'') from ''s''
let ''x'' = ''x1''
if '''Inside'''(''x'', ''y''):
while '''Inside'''(''x'' - 1, ''y''):
'''Set'''(''x'' - 1, ''y'')
''x'' = ''x'' - 1
if ''x'' < ''x1'':
Add (''x'', ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
while ''x1'' <= ''x2'':
while '''Inside'''(''x1'', ''y''):
'''Set'''(''x1'', ''y'')
''x1'' = ''x1'' + 1
if ''x1'' > ''x'':
'''Add''' (''x'', ''x1'' - 1, ''y'' + ''dy'', ''dy'') to ''s''
if ''x1'' - 1 > ''x2'':
'''Add''' (''x2'' + 1, ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
''x1'' = ''x1'' + 1
while ''x1'' < ''x2'' and not '''Inside'''(''x1'', ''y''):
''x1'' = ''x1'' + 1
''x'' = ''x1''
Where a path or boundary is to be followed, the right-hand rule is used. The painter follows the region by placing their right-hand on the wall (the boundary of the region) and progressing around the edge of the region without removing their hand.
For case #1, the painter paints (fills) the pixel the painter is standing upon and stops the algorithm.
For case #2, a path leading out of the area exists. Paint the pixel the painter is standing upon and move in the direction of the open path.
For case #3, the two boundary pixels define a path which, if we painted the current pixel, may block us from ever getting back to the other side of the path. We need a "mark" to define where we are and which direction we are heading to see if we ever get back to exactly the same pixel. If we already created such a "mark", then we preserve our previous mark and move to the next pixel following the right-hand rule.
A mark is used for the first 2-pixel boundary that is encountered to remember where the passage started and in what direction the painter was moving. If the mark is encountered again and the painter is traveling in the same direction, then the painter knows that it is safe to paint the square with the mark and to continue in the same direction. This is because (through some unknown path) the pixels on the other side of the mark can be reached and painted in the future. The mark is removed for future use.
If the painter encounters the mark but is going in a different direction, then some sort of loop has occurred, which caused the painter to return to the mark. This loop must be eliminated. The mark is picked up, and the painter then proceeds in the direction indicated previously by the mark using a left-hand rule for the boundary (similar to the right-hand rule but using the painter's left hand). This continues until an intersection is found (with three or more open boundary pixels). Still using the left-hand rule the painter now searches for a simple passage (made by two boundary pixels). Upon finding this two-pixel boundary path, that pixel is painted. This breaks the loop and allows the algorithm to continue.
For case #4, we need to check the opposite 8-connected corners to see whether they are filled or not. If either or both are filled, then this creates a many-path intersection and cannot be filled. If both are empty, then the current pixel can be painted and the painter can move following the right-hand rule.
The algorithm trades time for memory. For simple shapes it is very efficient. However, if the shape is complex with many features, the algorithm spends a large amount of time tracing the edges of the region trying to ensure that all can be painted.
A walking algorithm was published in 1994.
set cur to starting pixel
set cur-dir to default direction
clear mark and mark2 (set values to null)
set backtrack and findloop to false
'''while''' front-pixel is empty '''do'''
move forward
'''end while'''
jump to START
MAIN LOOP:
move forward
'''if''' right-pixel is inside '''then'''
'''if''' backtrack is true '''and''' findloop is false '''and''' either front-pixel '''or''' left-pixel is inside '''then'''
set findloop to true
'''end if'''
turn right
PAINT:
move forward
'''end if'''
START:
'''set''' ''count'' to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
'''if''' ''count'' '''is not''' 4 '''then'''
'''do'''
turn right
'''while''' front-pixel is inside
'''do'''
turn left
'''while''' front-pixel is not inside
'''end if'''
'''switch''' ''count''
case 1
'''if''' backtrack is true '''then'''
set findloop to true
'''else if''' findloop is true '''then'''
'''if''' mark is null '''then'''
restore mark
'''end if'''
'''else if''' front-left-pixel and back-left-pixel are both inside '''then'''
clear mark
set cur
jump to PAINT
'''end if'''
end case
case 2
'''if''' back-pixel is not inside '''then'''
'''if''' front-left-pixel is inside '''then'''
clear mark
set cur
jump to PAINT
'''end if'''
'''else if''' mark is not set '''then'''
set mark to cur
set mark-dir to cur-dir
clear mark2
set findloop and backtrack to false
'''else'''
'''if''' mark2 is not set '''then'''
'''if''' cur is at mark '''then'''
'''if''' cur-dir is the same as mark-dir '''then'''
clear mark
turn around
set cur
jump to PAINT
'''else'''
set backtrack to true
set findloop to false
set cur-dir to mark-dir
'''end if'''
'''else if''' findloop is true '''then'''
set mark2 to cur
set mark2-dir to cur-dir
'''end if'''
'''else'''
'''if''' cur is at mark '''then'''
set cur to mark2
set cur-dir to mark2-dir
clear mark and mark2
set backtrack to false
turn around
set cur
jump to PAINT
'''else''' if cur at mark2 '''then'''
set mark to cur
set cur-dir and mark-dir to mark2-dir
clear mark2
'''end if'''
'''end if'''
'''end if'''
end case
case 3
clear mark
set cur
jump to PAINT
end case
case 4
set cur
done
end case
'''end switch'''
end MAIN LOOP
|
|
